package Sort;

public class InsertSort {
    //插入排序
    public static void main(String[] args) {
        int[] arr={1,9,5,7,6,8,2,3,4,2,0,6};

        insertSort(arr);
        printarr(arr);
    }

    private static void insertSort(int[] arr) {
        //找到无序的起始索引
        int startindex=-1;
        for (int i = 0; i < arr.length; i++) {
            if(arr[i]>arr[i+1]){
                startindex=i+1;
                break;
            }
        }
        //外循环：拿出每一个无序的元素（从1元素开始）
        for (int i = startindex; i < arr.length; i++) {
            //内循环：和有序的元素从后往前进行比较
            for (int j =i-1 ; j >= 0 ; j--) {

                if(arr[j]>arr[i]){
                    int temp=arr[j];
                    arr[j]=arr[i];
                    arr[i]=temp;
                    i--;
                }
//                printarr(arr);
//                System.out.println();
            }
//            printarr(arr);
//            System.out.println();
        }

    }

    public static void printarr(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
    }
}
